home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 12721 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.7 KB
  1. Path: mail2news.demon.co.uk!genesis.demon.co.uk
  2. From: Lawrence Kirby <fred@genesis.demon.co.uk>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Question on 'bubble sort'
  5. Date: Tue, 02 Apr 96 12:22:29 GMT
  6. Organization: none
  7. Message-ID: <828447749snz@genesis.demon.co.uk>
  8. References: <4jieso$juc@lantana.singnet.com.sg> <828206958snz@genesis.demon.co.uk> <4jmv0d$t2p@news1.mnsinc.com> <4jp8mnINNmq0@keats.ugrad.cs.ubc.ca>
  9. Reply-To: fred@genesis.demon.co.uk
  10. X-NNTP-Posting-Host: genesis.demon.co.uk
  11. X-Newsreader: Demon Internet Simple News v1.27
  12. X-Mail2News-Path: genesis.demon.co.uk
  13.  
  14. In article <4jp8mnINNmq0@keats.ugrad.cs.ubc.ca>
  15.            c2a192@ugrad.cs.ubc.ca "Kazimir Kylheku" writes:
  16.  
  17. >In article <4jmv0d$t2p@news1.mnsinc.com>,
  18. >Szu-Wen Huang <huang@mnsinc.com> wrote:
  19. > >Lawrence Kirby (fred@genesis.demon.co.uk) wrote:
  20. > >: In article <4jieso$juc@lantana.singnet.com.sg>
  21. > >:            s8700055@singnet.com.sg "XY Xie" writes:
  22. > >
  23. > >: >I came across this sorting algorithm called 'bubble sort' in a book.
  24. > >
  25. > >: If the book doesn't explain why there is never a good reason to use bubble
  26. > >: sort then I suggest you get another book.
  27. > >
  28. > >Sure there is.  If I had 5 minutes to code something that will sort
  29. > >10 numbers, bubblesort comes in real handy.  If you've ever joined
  30. > >a programming contest you'll know what I mean.
  31.  
  32. You're still better off with insertion sort which is at least as simple.
  33.  
  34. >It's also good for sorting a fixed number of points. Say I had to sort the
  35. >three vertices of a triangle in order of increasing y coordinate. What you do
  36. >is just compare the first two points, possibly swap, then the last two points,
  37. >possibly swap and then compare the first two points again, possibly swapping.
  38. >
  39. >This is just a special case of the bubble sort and I have used it in polygon
  40. >drawing code.
  41.  
  42. Call it bubble sort if you will but that is also an insertion sort for 
  43. 3 elements (at least if the 3rd test is conditional on the 2nd).  The correct
  44. approach here is:
  45.  
  46.      if (a1 > a2)
  47.          swap(&a1, &a2);
  48.  
  49.      if (a2 > a3) {
  50.          swap(&a2, &a3);
  51.  
  52.          if (a1 > a2)
  53.              swap(&a1, &a2);
  54.      }
  55.  
  56. which averages 2 2/3 comparisons for random data and is clearly an insertion
  57. sort for 3 elements.
  58.  
  59. >The asymptotic complexity of algorithms matters little on any data set whose
  60. >size is fixed in advance, especially when the size is small. The precise size
  61. >at which the algorithm with better complexity surpasses the worse algorithm in
  62. >performance depends on the constants introduced by the implementation.
  63.  
  64. Constant factors can still be important. You may have many triangles to
  65. calculate for.
  66.  
  67. -- 
  68. -----------------------------------------
  69. Lawrence Kirby | fred@genesis.demon.co.uk
  70. Wilts, England | 70734.126@compuserve.com
  71. -----------------------------------------
  72.